package com.rr.middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author zhuangcanrun
 * @Date 2022/08/11/19:18
 * @description
 **/

/*
* 数组题：合并区间https://leetcode.cn/problems/merge-intervals/
* */
public class MergeInterval {
    public int[][] merge(int[][] intervals) {
        int length = intervals.length;
        if (length == 1) {
            return intervals;
        }

//        for (int i = 0; i < length - 1; i++) {
//            for (int j = 0; j < length - i -1; j++) {
//                int first = intervals[j][0];
//                int second = intervals[j + 1][0];
//                if (first > second) {
//                    swap(intervals, j, j + 1);
//                }
//            }
//        }

        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        int tempIntervalLeft = intervals[0][0];
        int tempIntervalRight = intervals[0][1];
        List<int[]> intervalList = new ArrayList<>();

        for (int i = 1; i < length; i++) {
            if (intervals[i][0] <= tempIntervalRight) {
                tempIntervalRight = Math.max(intervals[i][1], tempIntervalRight);
            } else {
                intervalList.add(new int[]{tempIntervalLeft, tempIntervalRight});
                tempIntervalLeft = Math.max(intervals[i][0], tempIntervalLeft);
                tempIntervalRight = Math.max(intervals[i][1], tempIntervalRight);
            }
        }
        intervalList.add(new int[]{tempIntervalLeft, tempIntervalRight});

//        int size = intervalList.size();
//        int[][] ans = new int[size][2];
//        for (int i = 0; i < size; i++) {
//            ans[i] = intervalList.get(i);
//        }
//        return ans;
        return intervalList.toArray(new int[intervalList.size()][]);
    }
    private void swap(int[][] intervals, int i, int j) {
        int temp[] = intervals[i];
        intervals[i] = intervals[j];
        intervals[j] = temp;
    }

    public static void main(String[] args) {
        MergeInterval mergeInterval = new MergeInterval();
        mergeInterval.merge(new int[][]{{4, 5}, {1, 4}, {0, 1}});
    }
}
